package com.lx.algorithm.Tree;

import java.util.ArrayList;
import java.util.UnknownFormatConversionException;

import static com.lx.algorithm.Tree.TreeUtils.generateRandomBST;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-19 16:36:04
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-19     张李鑫                     1.0         1.0 Version
 */
public class MaxSubBSTSize {


    public static class NodeInfo {
        public int max;
        public int min;
        public int nodes;
        public int allSize;
        public boolean isBST;

        public NodeInfo(int max, int min, int nodes, int allSize, boolean isBST) {
            this.max = max;
            this.min = min;
            this.nodes = nodes;
            this.allSize = allSize;
            this.isBST = isBST;
        }
    }


    public static int maxSubBSTSize(Node node) {
        long l = System.currentTimeMillis();
        if (node == null) {
            return 0;
        }
        int nodes = process(node).nodes;
        System.out.print(System.currentTimeMillis()-l);
        System.out.print("      m");
        System.out.println();
        return nodes == 0 ? 1 : nodes;
    }

    public static NodeInfo process(Node node) {
        if (node == null) {
            return null;
        }
        NodeInfo leftInfo = process(node.left);
        NodeInfo rightInfo = process(node.right);
        int max = (int) node.value;
        int min = (int) node.value;
        int allSize = 1;


        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
            allSize += rightInfo.allSize;
        }
        boolean isBST = true;
        if (leftInfo != null && leftInfo.max >= (int) node.value) {
            isBST = false;
        }
        if (rightInfo != null && rightInfo.min <= (int) node.value) {
            isBST = false;
        }
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }
        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }
        int nodes = 1;
        if (isBST) {
            if (leftInfo != null) {
                nodes += leftInfo.allSize;
            }
            if (rightInfo != null) {
                nodes += rightInfo.allSize;
            }
        } else {
            nodes = Math.max(leftInfo != null ? leftInfo.nodes : 0, rightInfo != null  ? rightInfo.nodes : 0);
        }

        return new NodeInfo(max, min, nodes, allSize, isBST);
    }

    public static int maxSubBSTSize1(Node head) {
        long l = System.currentTimeMillis();

        if (head == null) {
            return 0;
        }
        int h = getBSTSize(head);
        if (h != 0) {
            return h;
        }
        int max = Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
        System.out.print(System.currentTimeMillis()-l);
        System.out.print("      t");
        System.out.println();
        return max;
    }

    public static int getBSTSize(Node head) {
        if (head == null) {
            return 0;
        }
        ArrayList<Node> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if ((int) arr.get(i).value <= (int) arr.get(i - 1).value) {
                return 0;
            }
        }
        return arr.size();
    }

    public static void in(Node head, ArrayList<Node> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }


    public static void main(String[] args) {

//        Node<Integer> node = new Node<>(98);
//        Node<Integer> node1 = new Node<>(70);
//        Node<Integer> node3 = new Node<>(72);
//        Node<Integer> node4 = new Node<>(69);
//        Node<Integer> node5 = new Node<>(52);
//        Node<Integer> node6 = new Node<>(68);
//        Node<Integer> node7 = new Node<>(93);
//        Node<Integer> node8 = new Node<>(87);
//        Node<Integer> node9 = new Node<>(71);
//        Node<Integer> node10 = new Node<>(3);
//        node.left = node1;
//        node1.left = node3;
//        node3.left = node4;
//        node1.right = node5;
//        node5.right = node6;
//        node.right = node7;
//        node7.left = node8;
//        node8.left = node9;
//        node8.right = node10;
//
//        System.out.println(maxSubBSTSize(node));
        int maxLevel = 120;
        int maxValue = 100;
        int testTimes = 100;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (maxSubBSTSize(head) != maxSubBSTSize1(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

    public static void demo() {
        Node<Integer> node = new Node<>(98);
        Node<Integer> node1 = new Node<>(70);
        Node<Integer> node3 = new Node<>(72);
        Node<Integer> node4 = new Node<>(69);
        Node<Integer> node5 = new Node<>(52);
        Node<Integer> node6 = new Node<>(68);
        Node<Integer> node7 = new Node<>(93);
        Node<Integer> node8 = new Node<>(87);
        Node<Integer> node9 = new Node<>(71);
        Node<Integer> node10 = new Node<>(3);
        node.left = node1;
        node1.left = node3;
        node3.left = node4;
        node1.right = node5;
        node5.right = node6;
        node.right = node7;
        node7.left = node8;
        node8.left = node9;
        node8.right = node10;

    }


}
